/*
 * @lc app=leetcode.cn id=315 lang=golang
 *
 * [315] 计算右侧小于当前元素的个数
 */

// @lc code=start
// package t

type node struct {
	index, val int
}

func countSmaller(nums []int) []int {
	n := len(nums)
	nodes := make([]node, 0, n)
	for i, v := range nums {
		nodes = append(nodes, node{i, v})
	}
	res := make([]int, n)
	dfs(&nodes, 0, n, &res)
	return res
}

// 使用归并排序计算逆序对的方式，计算该题
func dfs(nodes *[]node, l, r int, res *[]int) {
	if l >= r-1 {
		return
	}
	mid := (l + r) / 2
	dfs(nodes, l, mid, res)
	dfs(nodes, mid, r, res)
	merge(nodes, l, mid, r, res)

}

func merge(nodes *[]node, l, mid, r int, res *[]int) {
	// if l >= r-1 {
	// 	return
	// }
	p, q := mid-1, r-1
	tmp := make([]node, 0, r-l)
	for p >= l && q >= mid {
		if (*nodes)[p].val > (*nodes)[q].val {
			(*res)[(*nodes)[p].index] += q - mid + 1
			tmp = append(tmp, (*nodes)[p])
			p--
		} else {
			tmp = append(tmp, (*nodes)[q])
			q--
		}
	}
	for p >= l {
		tmp = append(tmp, (*nodes)[p])
		p--
	}
	for q >= mid {
		tmp = append(tmp, (*nodes)[q])
		q--
	}
	// 注意此处是使用 l 开始
	for i, j := l, len(tmp)-1; j >= 0; i, j = i+1, j-1 {
		(*nodes)[i] = tmp[j]
		// fmt.Println(tmp, *nodes)
		// tmp[i], tmp[j] = tmp[j], tmp[i]
	}
	// (*nodes)[l:r] = tmp[:r-l]

}

// @lc code=end
